HPAVC/HPAVC CD-ROM.iso/CIS_GAME.ARJ/QCOLL1.THD

Text File | 1993-07-01 | 39KB | 832 lines

_________________________ Subj: Collision Detection _________________________

Fm: Mark Betz/GD SL 76605,2346                 # 172652
To: David J. Leach Jr 70511,1573               Date: 29-May-92  17:50:56

...
There are two methods I'm familiar with for collision detection. One is
simply based on range checking. That is, if a ball is 10 x 10 pixels, and a
wall is at y = 50, then if the ball's position is at y = 41 you have hit the
wall. Another method that was described here recently is interesting. In this
method specific colors are reserved for parts of the game, and you test for a
collision by testing the color value of pixels you are overwriting.
                                                       --Mark
...........................................................................

Fm: Tim Triemstra 70007,6361                   # 172779
To: Mark Betz/GD SL 76605,2346 (X)             Date: 29-May-92  23:27:10

One final way is for all you people that work in a vector world.  The array
method is of course the best (if you KNOW you're touching something, it's
easy to react)  However, in games like Wolfenstein 3D and Ultima Underworld
you are dealing with HUGE worlds, and an unlimitted number of locations.

In these cases you'd have to use right-triangle trig to determine the outcome
of a sentence like:

"In 3 seconds the character will move approximately 3 units from the current
position.  At this angle the hypotoose (sp?) would be 3 units.  Use this
distance to determine the offset in the Y and X planes.  Run the same check
on the wall <ie: wall distance and angle>.  Do a check to see if the two
points at the end of the calculation are in the same space."

This is much more complex, but if you develop a game with an unlimitted
number of locations it would be great to develop a set of routines for
maintaining objects within a world like this.  This method is by FAR the most
adjustable.

Hopefully this didn't confuse you too much, but it could't hurt to ask a
question or two now that I've made it alot more complex.  I'm always willing
to dig out my calc book.

Tim T.
...........................................................................

Fm: yngvi 76703,3046                           # 173700
To: Tim Triemstra 70007,6361 (X)               Date: 01-Jun-92  14:13:06

I used a similar method for collision detection in one of my early games
-hwoever, you can skip some of the calculations by defining an approximation:

briefly, consider a point A, approaching a line B-C.  this forms a triangle,
with the B-C as the base. as the point comes closer, the combined length of
the two lines from the point begin to approach the value of the line itself:
       A-B + A-C --> B-C

  you can do rough calcs of the line lengths, and dont need to use the
pythagorean equation (with square roots).  This was published as an article
in Computer Language about 5 or so years ago.

  Another trick is to do some rough calcs first to see if the two objects are
even worth investigating.

  There are also some point, polygon intersection algorithms that can be used
for more precise details.
...........................................................................

Fm: Stuart Patterson 76507,1602                # 188687
To: All                                        Date: 17-Jul-92  11:09:04

Well here I go again.

I've been trying to figure the best method for Collision Detection.
One method I come up with is to use the lower 128 colors to represent
background and none destructive objects then use the upper 128 to represent
objects which can be collided with.  This method seems ok
in 256 color mode (13h).  Does anyone have any thoughts on better
methods?  I know you guys don't use this method in 16 color mode!

thanks,

stuart patterson
...........................................................................

Fm: Mark Betz/GD SL 76605,2346                 # 188802
To: Stuart Patterson 76507,1602 (X)            Date: 17-Jul-92  18:24:40

Hi, Stuart. I think Dan has used that color-based detection method. Most of
the simpler animations I've seen have used range-checking, which means dpo
compares against the other objects in the vicinity. I've used this technique
myself, and it can be pretty fast. Usually most of the surfaces and objects
in a frame can be rejected by trivial tests (the wall is on the other side of
the room, etc). When you get down to the few objects you might be colliding
with you check for coordinate overlap.

                                                        --Mark
...........................................................................

Fm: Dan R Corritore 70243,1110                 # 189539
To: Mark Betz/GD SL 76605,2346 (X)             Date: 19-Jul-92  23:05:22

<<I think Dan has used that color-based detection method.>>
        NOT!!! It was Rasch, Rasch, Rasch!!! Don't give me the credit!

I use the method of floor-maps, and events. The floor maps are just bit masks
which have bits set where there is an object. The latter, events is
everything that is not a stationary object, OR/AND any area in which some
activity will occur when the current sprite enters the bounds.(Say, walking
into the range of a motion detector..which could trigger doors to open,bells
to alarm, fat lady's to sing, etc.).
        _Dan
...........................................................................

Fm: Mark 'SAM' Baker 100025,444                # 189767
To: Stuart Patterson 76507,1602 (X)            Date: 20-Jul-92  17:18:41

Using the first 128 colours can work; but I find it's better to use the
colours for 'planing' the screen; breaking down into blocks of 64
colours/plane: and to use co-ordinates for collision detection (though this
means using 3-d coordinates.
                                                Mark
...........................................................................

Fm: Dan R Corritore 70243,1110                 # 189886
To: Mark 'SAM' Baker 100025,444                Date: 20-Jul-92  22:40:44

<<and to use co-ordinates for collision detection (though this means using
3-d coordinates.>>

        Using coordinates for collision detection hardly requires you to use
3-d coordinates, unless you are doing some specific 3-d game.. My game system
has a 'sorta kinda 3-d system', but its collision detection is just with
X-Y-coordinates. So far,this means that even if a sprite is jumping way up in
the air, it will still be detected by someone on the ground. I've done a
little compensating for that, though (well, there just HAS to be birds in the
game), but, for the most part, its 2-d. A good example of a coordinate-non-3d
collision detection method is of racing cars viewed from a
birds-eye-perspective. The cars image and its spot on the ground are both the
same, so if the image crashes into something, so does the car. But if the
cars going diagonally, the collision detection would have to go a little
further to ensure an 'exact' hit,because of the space on the sides--in which
color detection could work.
        _Dan
...........................................................................

Fm: Dan R Corritore 70243,1110                 # 190751
To: Mark 'SAM' Baker 100025,444 (X)            Date: 23-Jul-92  00:55:27

I am doing the same type of work you are, although slightly different. I have
the possibility of each sprite being behind 14 different masks, and the masks
are not done with special colors. The masks are separate from the image,
therefore giving more flexibility and no restrictions. The way I have the
masks is that each bit represents one pixel on the screen(but for the current
mask). I was thinking of changing this to a more flexible implementation, but
it would slow down the animation, and I want to keep my speed.This more
flexible implementation(which doesn't increase the size of memory needed to
store it) allows 256 total masks to be implemented. But, for now, 14 masks
seems good enough to me.
For my system,if a sprite is behind a bush and another is in front of it, and
they are headed straight for each other, collision won't be an issue, since
the bush is defined in the floor mask as a permanent object, and the sprites
would stop moving once they hit the bush. I could also define the bush as a
temporary object, and the other sprites would just bang into the bush-that
being their collided object.
        _Dan
...........................................................................

Fm: Dan Corritore 70243,1110                   # 266746
To: KGliner 70363,3672                         Date: 23-Dec-92  13:59:48

This is in response to a message you posted to me a while ago. I was just
looking through some old messages and deleting them, when I came across
yours(again). I've been thinking about it, and have decided not to use what
you said..(which I wasn't going to anyway)..

You said to have the sprites connected to the tiles in a tile-based-world for
faster collision detection. This would require about 4 bytes per tile (or, if
used efficiently, 2 bytes)..which would be tacked on right after the tile
index (of course). Anyway, it's possible that this scheme will fail, and
Murphy's Law states that if it can fail, it will! <G> Anyway, saying you have
a sprite that spreads across 2 or more tiles.. you stated that you would only
require one tile to point to the sprite..this isn't smart at all, since when
checking for collision detection it is definitely possible to miss a sprite
like this (especially if, say, the sprite was spread across 4 tiles).
Connecting every tile that it covers to it (by pointing them all to the
sprite) corrects this problem, but it imposes another problem. If you have
more than one sprite on a tile, you would need to have a linked list, and
when a sprite has 2 or more tiles connected to it, it's impossible for the
sprite to know how many pointers it should have to next sprites. Unless, of
course, you create an array of pointers (with a pointer to that array, and a
number indicating how many pointers you have).. well, anyway, you get the
picture..it would be too complicated to keep it failsafe..even if it is a
very unlikely thing to happen. So, what's your take on this?
        _Dan
...........................................................................

Fm: Dan Corritore 70243,1110                   # 270060
To: KGliner 70363,3672 (X)                     Date: 30-Dec-92  00:08:40

<Slapping self in head> Duh, I should have thought of that!<G> It won't be
that much harder to check a few extra tiles around the collision area, but it
might make it a wee bit slower.. Ok, say if your tiles were 16*16, and your
biggest sprite was 20*20, this would require, using the worst case scenario,
checking 3 x * 3 y = 9 tiles, being that the tile pointer to the sprite could
start in that big area. Diagram below: (backslashes is the area taken up by
the sprite)

   |          |          |          |
   |        \\\\\\20x\\\\\\\        |
   |        \ |          | \        |
   |---16x--\-|----------|-\--------|
   |        \ |          | \        |
   |        \ |          | 20       |
  16        \ |  Inside  | y        |
   y        \ |          | \        |
   |        \ |          | \        |
   |--------\-|----------|-\--------|
   |              \ |          | \        |
   |        \\\\\\\\\\\\\\\\        |

Hopefully that came out right. If not, it was a 3*3 box of 16*16 tiles with a
20*20 figure in the middle of them all..a possible situation. So, tell me
now, is it still worth all that extra memory to use this collision detection
scheme? Have you tested this out already? Thanks,
        _Dan
...........................................................................

Fm: KGliner 70363,3672                         # 270127
To: Dan Corritore 70243,1110 (X)               Date: 30-Dec-92  03:54:55

   Well, if you only have to do 9 collision checks per moving object (and
simple checks too as they involve only seeing if a ptr is nil), and you have
100 moving objects, then that's 900 checks per cycle.  Much better than
comparing 100 objects to 99 others for 9900 checks per cycle (and those would
be far more complicated than just seeing if a ptr is nil).

   Now, in the example you give, I'd say you'd need four pointers for the
sprite because it is larger than your tile size in both dimensions by more
than 1x but less than 2x.  This isn't going to be terribly efficient if
you've got a lot of 20x20 sprites and want to work with 16x16 tiles.  Better
to just make your tiles 20x20.

   As for how practical this is depends a lot on the specifics of what you
want to do. If your largest sprite is only 40x40, then make all your tiles
40x40 too, and you never have to have more than one ptr to a sprite (although
you still need to be able to have more than one ptr from a tile to multiple
sprites on the tile).  The larger the tiles, the less memory you use, but the
more sprites that might actually be on that tile (having no effect on this
stage of collision detection but slowing down the next stage when you do more
complicated checks).  How efficient this is depends on how many sprites you
typically have moving at once, how crowded the sprites are likely to get, and
just how big the sprites actually are.

   I haven't tried to implement any of this, and unfortunately I probably
won't since I don't think any of the designs I want to do would require such
a scheme (hey, I'm just making this up as I go).  I have used tiles w/ptrs to
sprites before, but only in a strategy game where the sprites couldn't
overlap the tiles.

   Hope that answers your question...     Kevin
...........................................................................

Fm: Dan Corritore 70243,1110                   # 270424
To: KGliner 70363,3672 (X)                     Date: 30-Dec-92  16:13:17

<<   As for how practical this is depends a lot on the specifics of what you
want to do. If your largest sprite is only 40x40, then make all your tiles
40x40 too, and you never have to have more than one ptr to a sprite..>>

Even with sprites the same size as the tiles, you have the possibility of it
overlapping 4 different tiles at a time. Sure it's less, but it's still the
same tough spot. I think I'll try both ideas to see which one works
faster/better. If you don't remember what the other idea was, it was checking
for collision using a tree, and the tree would be divided up into equal
sections.. what I mean, is that if your tile world is 32000 pixels wide by
32000 pixels high, the first tree node would be at 16000,16000, then from
16000,16000 go half again, etc.. until you reach a good enough number. Thanks
again,
        _Dan
...........................................................................

Fm: KGliner 70363,3672                         # 270579
To: Dan Corritore 70243,1110 (X)               Date: 30-Dec-92  20:54:19

Dan-  I'm not sure I understand the problem that arises from having a sprite
overlap 4 tiles.  As long as only one of the tiles points to the sprite, and
this tile is the one most overlapped by the sprite, and you check the
surrounding 8 tiles when doing collision checks, then it's impossible for a
collision to be missed.  And it still only costs you a maximum of 9 checks
per object that actually moves.

  Kevin
...........................................................................

Fm: Dan Corritore 70243,1110                   # 270740
To: KGliner 70363,3672 (X)                     Date: 31-Dec-92  00:09:10

<< I'm not sure I understand the problem that arises from having a sprite
overlap 4 tiles.>>

Well, for one, it adds a level of complexity! I know, it shouldn't make a
difference to a 'real' programmer, but right now, I'm going to go with the
simpler tree method I said.. if it's too slow I'll consider your approach,
but only if I have the memory to spare(and want to take the time to do the
extra tile collision checks). Thanks for the idea, though..
         _Dan
...........................................................................

Fm: Mark Hula 100047,110                       # 318482
To: All                                        Date: 22-Mar-93  14:40:08

Hi All,

I'm scrolling a large map 2 pixels in any direction and I want to perform
collision detection against the scenery.The main character is always in the
centre (doesn't physically move).I guess I could store all the x+y's of all
'solid' scenery (all scenery is square as such) and simply see if the main
characters "square box" has gone into one of the scenery but this seems tacky
and inefficent,does anyone know of a better solution???? Not colour
checking!-thats even tackier!

Thanks

MC
...........................................................................

Fm: Dan Corritore 70243,1110                   # 318540
To: Mark Hula 100047,110 (X)                   Date: 22-Mar-93  16:24:14

I'm not sure what you mean by 'tacky'.. that's a good enough solution for you
to use, but if you mean it's not fast enough (if there's too many things to
check against), than I'll give you a solution someone else gave me! (I won't
give you any names, but his intials are Kevin Gliner!<g>) Actually, he gave
me a different solution, but it's pretty close to what he suggested. Just
divide the landscape into sections, preferably having the sections be the
size of the largest object you'll use, and then have the objects 'connected'
to the section they are in. For doing collision detection this way, you'd
need to only check a few sections instead of the whole map. In some cases,
this might take up too much space.. so you should judge for yourself whether
or not this is the best approach. Another approach is to have all the objects
connected in a tree, but that's a bit more complicated, since you must keep
the x1,y1-x2,y2 locations for the objects. And finally, another last approach
would be to have the landscape tiled, so that you can have tiles with
optional 'walk/no-walk' areas.
        _Dan
...........................................................................

Fm: Danator 71601,3551                         # 336877
To: Game Programers                            Date: 18-Apr-93  17:44:19

Hello all,

     I have a quistion about detecting colissions in arcade games and in 3D
applications.  I've allmost driven myself crazy trying to figure this out and I
havent been able to find any kind of reference material that deals with it.
This is suprizing because collision detection plays a very important role in
games.  I used to have a AMIGA computor and a simple language called AMOS
that had routines that handled collisions. That was nice but now I have a PC
and am using C.  I also use Fastgraph but, it doesn't have routines for
detecting collisions.

 Anyway, I felt that this was probably the best place to come to find out. I
am sure that there are several others who would like to know how it's done,
so I think it would be a good thread for disscusion.

   If you've got some neat tricks or even not so neat tricks, let the rest of
us poor souls in on them.
                               Thanks a million,
                               Dan Weatherman
                               71601,3551
...........................................................................

Fm: John Dlugosz [ViewPoint] 70007,4657        # 337148
To: Danator 71601,3551 (X)                     Date: 18-Apr-93  21:29:01

Can you be more specific?  Colliding with walls is easy.  Colliding with
other objects is also easy, but there are ways to make it faster.

--John
...........................................................................

Fm: Mark Betz/Ass't SysOp 76605,2346           # 337469
To: John Dlugosz [ViewPoint] 70007,4657 (X)    Date: 19-Apr-93  13:00:12

I'm interested in this topic. For rudimentary collision detection I would
probably think to compare bounding rectangles, but for some sprites this
would result in some unrealistic collisions. I've thought about using masks
with a 1 bit for each non-transparent pixel in the sprites, and then ANDing
the intersection together to see if anything came out set. I'm not sure this
would be fast enough, though. At least one person here was using a
color-based scheme at one point, where specific colors were reserved to
specific sprites and objects. I think he abandoned it eventually.

                                                        --Mark
...........................................................................

Fm: Dan Corritore 70243,1110                   # 337479
To: Mark Betz/Ass't SysOp 76605,2346 (X)       Date: 19-Apr-93  13:42:04

You're speaking of Rasch, yes? I remember him mentioning that he reserved
specific colors for sprites and objects, and would do collision detection
based on what colors hit others, or somesuch. I believe he said he did it
because he did some sort of complex rotation on the sprites, making it hard
to figure out their masks/positions. It was a neat idea, to say the least!
Anyway, you say he abandoned the idea? Thanks,
        _Dan
...........................................................................

Fm: Bob Provencher/GD SL 71621,2632            # 337863
To: Mark Betz/Ass't SysOp 76605,2346 (X)       Date: 19-Apr-93  22:53:33

Hi Mark -

I use the intersection of the bounding rectangle first to determine if it's
necessary to and the masks together.  What I found that was usually, if the
rectangles intersected you found a 1 in the ANDed mask fairly quicky.  Worst
case was if the was no intersection, and then you ended up searching the
entire ANDed mask.  That happened with odd shaped objects, say like a ring.

It still worked out pretty well, even in Windows <g>.

Bob
...........................................................................

Fm: Mark Betz/Ass't SysOp 76605,2346           # 337922
To: Bob Provencher/GD SL 71621,2632            Date: 20-Apr-93  00:41:18

That makes sense, Bob. Always perform the simple test for trivial rejection
first, and the drop through to the more specific comparisons on the result
set. See, you can learn how to program games while doing database design <g>.
                                                         --Mark
...........................................................................

Fm: Bob Provencher/GD SL 71621,2632            # 337220
To: Danator 71601,3551 (X)                     Date: 18-Apr-93  23:24:08

Hi Danator,

Welcome to GAMERS!  What I usually do is first test that the bounding
rectangles of the two objects intersect, then check that the masks of the
two objects overlap.

Others will probably jump in with more, if you need more specifics, just
ask.

Bob
...........................................................................

Fm: Teut Weidemann 100022,2466                 # 337290
To: Bob Provencher/GD SL 71621,2632 (X)        Date: 19-Apr-93  02:04:10

For fast action games (50-60 frames/sec) checking with the collision mask is
too time consuming. Checking with a frame that is smaller than the object
itself fills the need.
The most importand "rectangle" is that of your character in the game (ie.
MArio or Sonic). In our games it helped a lot to sort all objects along their
YX coordinates (which was one word). So we tested all objects top to down
only that far: Y+YSize. this saved a lot of time. Actually sorting all
objects helped with 8 directional scrolling, too. But thats another story.
Teut
...........................................................................

Fm: Jaimi the OverTaxed 71700,1202             # 337696
To: Danator 71601,3551 (X)                     Date: 19-Apr-93  19:59:37

Dan, Here's a simple algorithm to check if two boxes intersect. It's part of
a box class that I wrote, but it's pretty much self explanatory. Its main
advantage being its very fast. I just shopped this out of some code so you'll
have to tidy it up. this actually calculates a box that is the union of two
boxes. if the boxes intersect, the width (w) will be positive.

void BOX::Union(BOX &bx1,BOX &bx2)
   {
   x=MAX(bx1.x,bx2.x);
   y=MAX(bx1.y,bx2.y);

   w = MIN(bx1.x2,bx2.x2)-x;
   h = MIN(bx1.y2,bx2.y2)-y;

   if ( w > 0 && h > 0 ) SetBox(x,y,w,h);
   else                  SetBox(0,0,0,0);
   }

P.S. It looks all formatted correctly from here, but you know how these
message editors are. by the time CIS reformats it may look like junk.
...........................................................................

Fm: Bob Provencher/GD SL 71621,2632            # 337865
To: Danator 71601,3551                         Date: 19-Apr-93  22:53:44

Hi Danator -

Here's how I normally detect intersection between two rectangles. In C++,
assuming we have a Rect class:

Assume you've defined a min and max, and that 0, 0 is the lower left corner
of the screen:

int Rect::isIntersect( Rect r )
{
    return max( left,   r.left )   <= min( right, r.right ) &&
           max( bottom, r.bottom ) <= min( top,   r.top );
}

If you'd like the intersecting rectangle:

Assume a constructor: Rect( int left, int top, int right, int bottom );

Rect Rect::Intersect( Rect r )
{
    if ( isIntersect( r ) )
        return Rect( max( left,  r.left ),  min( top,    r.top ),
                     min( right, r.right ), max( bottom, r.bottom ) );
    else
        return Rect( 0, 0, 0, 0 );
}

For the union:

Rect Rect::union( Rect r )
{
    return Rect( min( left,  r.left ),  max( top, r.top ),
                 max( right, r.right ), min( bottom, r.bottom ) );
}

ANDing the masks together is another story, and can depend a little on the
libs you're using.

Hope this helps!
Bob
...........................................................................

Fm: John Dlugosz [ViewPoint] 70007,4657        # 337782
To: Jaimi the OverTaxed 71700,1202 (X)         Date: 19-Apr-93  21:22:13

Mine is a little more efficient.  It does not calculate the union if the
boxes _don't_ intersect, but leaves the result in an undefined state.

In fact, it does the whole thing in one statement!

--John
...........................................................................

Fm: Jaimi the OverTaxed 71700,1202             # 337869
To: John Dlugosz [ViewPoint] 70007,4657 (X)    Date: 19-Apr-93  23:07:01

Yes, john. But leaving a box in an undefined state can lead to errors!

Jaimi
...........................................................................

Fm: John Dlugosz [ViewPoint] 70007,4657        # 337781
To: Danator 71601,3551                         Date: 19-Apr-93  21:22:06

How about:    if (intersection (r1,r2, result)) { ...

 bool intersection (twocorner *a, twocorner *b, twocorner *result)
 /* finds the intersection of 2 boxes and returns
    TRUE if intersection exists. */
 {
 return (
 (result->ul.x= (a->ul.x > b->ul.x) ? a->ul.x : b->ul.x /* left */) <=
 (result->lr.x= (a->lr.x < b->lr.x) ? a->lr.x : b->lr.x /* right */) &&
 (result->ul.y= (a->ul.y > b->ul.y) ? a->ul.y : b->ul.y /* top */) <=
 (result->lr.y= (a->lr.y < b->lr.y) ? a->lr.y : b->lr.y /* bottom */));
 }

       - or -

 bool window_core::intersection (
                   const twocorner& a,const twocorner& b,twocorner* result)
 // finds the intersection of 2 boxes and returns
 //   TRUE if intersection exists.
 {
 return (
 (result->ul.x= (a.ul.x > b.ul.x) ? a.ul.x : b.ul.x /* left */) <=
 (result->lr.x= (a.lr.x < b.lr.x) ? a.lr.x : b.lr.x /* right */) &&
 (result->ul.y= (a.ul.y > b.ul.y) ? a.ul.y : b.ul.y /* top */) <=
 (result->lr.y= (a.lr.y < b.lr.y) ? a.lr.y : b.lr.y /* bottom */));
 }
...........................................................................

Fm: Teut Weidemann 100022,2466                 # 337976
To: Danator 71601,3551                         Date: 20-Apr-93  01:40:17

Hmmm, this depends on how you organize your OBJ. Lets say you have two linked
lists. One for used (on screen) objecs, one for the empty slots for objects
to be displayed.
If you sort them by Y (then X) you can start with the first object and look
through the list and check their bounding rectangles till the next objects Y
is farer then your Y plus your Y-Size. Then go to the next OBJ.
This is ONLY neccessary if you have to check every OBJ with every objects.
But thats seldom the case. If you have only some objects to check (your
player plus bullets) you have to mark them or keep them separate to minimize
CPU time.
Teut
...........................................................................

Fm: Teut Weidemann 100022,2466                 # 337979
To: Bob Provencher/GD SL 71621,2632            Date: 20-Apr-93  01:45:37

Yes, I mean the smallest rectangle inside an object (most sprites are 16x16
or 32x32 anyway).
The only drawback can be seen as an enhacement of gameplay: If two objects
intersect but the rectangles dont, the play got just lucky enough to prevent
a collsion. You see that in most coin up games when you nearly miss an
object. Masking is ONLY done in fast action games if it depends on gameplay,
but I know only a few games who do this.
In Turrican (for Amiga, SNES, Megadrive) they use this technology along with
sorting all objects along their YX axis. This is only neccessary if you need
to check coll. between ALL objects, which is seldom the case. If you need to
check your player and your bullets, you have to keep them separate of mark
them accordingly.
Note: Our actio games are all 100% assembler. Our techies always try to do
everything in 50/50 frames a sec.
Teut
...........................................................................

Fm: Teut Weidemann 100022,2466                 # 338684
To: Bob Provencher/GD SL 71621,2632 (X)        Date: 21-Apr-93  01:17:24

I meant the smallest bounding rectangle inside an object, but that can vary.
We try to resize the rectangle accorningly to the objects looks an purpose,
ie. if it is a shot, the rectangle can be pretty small.
I worked the the largest publisher in germany (Softgold/Rainbow Arts) as the
development director (is that the american name for that job?) and we had
some good action titles.
Now I am in the games buisiness for advertising, ie. we are developing games
for advertising cutsomers like SONY, BLAUPUNKT, germany government, Kraft and
more.
In germany the deleoper "circle" is still pretty small and only a few got to
match the world standard.
Teut
...........................................................................

Fm: Mark Hula 100047,110                       # 338205
To: All                                        Date: 20-Apr-93  13:39:51

Hi All!

I'm trying to work out this problem and its really confusing my brain -
though I expect its all easy to you lot! :-) The problem is difficult to
explain but I'll try: Imagine a 10*10 square,in this square certain blocks
are set at random, for example the top left of the square may be:

  0 1 2 3 4 5
 -------------- 0! ! !*!*!*! ! 1! ! !*!*! ! !   An * indicates a block 'set'
2! ! ! ! ! !*!

What I'm looking for is a routine (algorithm no code will do) to search this
whole 10*10 map and produce the most optimized groupings into
squares/rectangles of blocks as possible (confused!) Take the ***  pattern,
this can be a *** followed by a ** or a ** and a *.
         **                                                   **

I know its not clear!,in that above example of course either choice would do
as the "shape" can only be divided into 2 "square" possiblities.But the shape
** optimally could be a ** and a *.i.e. don't want 3 ** and a *.!!!!!
      **                      **
      **                      **
      *

Clear as mud!-I know!!,if your wondering what the heck this is all for well!,
its for a collision routine!.Findings "squares" isn't too tricky ,finding
optimal ones is-it makes my head hurt!

Any help much welcome!!

MC
...........................................................................

Fm: Mark Hula 100047,110                       # 338891
To: Mark Hula 100047,110                       Date: 21-Apr-93  13:05:46

!-yep the picture is wrong!
 012345 0  ** 1  *** 2  *

i.e. blocks could be ** and *** and *,but whats the optimal way to find them
(the least number)-the above could also be a **
                                                  ** and 2 *.
...........................................................................

Fm: Mark Hula 100047,110                       # 345381
To: All                                        Date: 01-May-93  06:51:59

Having downloaded Tume it is indeed excellent! I noticed how the contours
were used for collision detection. Anybody got any ideas on exactly how these
are used for such,is it simply a certain colour used for collision detection?

MC
...........................................................................

Fm: Dan Corritore 70243,1110                   # 346709
To: Mark Hula 100047,110 (X)                   Date: 02-May-93  23:03:50

I'd assume that they used a mask for the collision detection. If you
remember, the collision layer was placed 'over' the tiles, so you could see
it..of course, in a game, that would look quite silly! Anyway, I don't like
the way they allow you to hook any collision tile to any place on the map.. I
mean, I like to have the color tiles themselves holding the collision stuff,
not the map.. if you would ever need to have a different sort of collision
mask for the tile(which is probably quite rare), you'd just declare a new
tile connected to the new mask. This would keep the size down (instead of
having an extra map(for the collision indexes), you have just a few more
tiles). Did you understand that?
        By the way, did you notice that the program was slow? I have a 386sx
16 mhz computer, and it ran pretty slowly, from what I remember. Well,
anyway, after playing around with their editor for a little while, I decided
to do my own.. who knows, you might decide to do the same!<g>
        _Dan
...........................................................................

Fm: Mark Hula 100047,110                       # 346838
To: Dan Corritore 70243,1110 (X)               Date: 03-May-93  04:26:23

Hi,

Not sure I understand you on how the collisions work within tUME. It ran fast
enough on my machine...50Mhz 486! <g>

MC
...........................................................................

Fm: Randy @ Safari 71165,3600                  # 346914
To: Dan Corritore 70243,1110 (X)               Date: 03-May-93  09:55:34

Actually, the TUME method of collission detection is quite advanced. I prefer
it because the mask only takes up 128 bytes as opposed to 256+128 for a 16x16
tile + mask. Besides, it only takes two machine instructions to find and read
the mask.

Randy
...........................................................................

Fm: Dan Corritore 70243,1110                   # 346983
To: Randy @ Safari 71165,3600 (X)              Date: 03-May-93  13:32:07

<<Actually, the TUME method of collission detection is quite advanced. I
prefer it because the mask only takes up 128 bytes as opposed to 256+128 for
a 16x16 tile + mask. Besides, it only takes two machine instructions to find
and read the mask.>>

I don't understand.. I thought they had as many collision masks as they did
tile indexes in the map. If so, then adding the mask data would double the
size of the world map! There is no benefit to that, let me tell you! Instead,
using what I mentioned (connecting the mask to the tile, and creating a new
tile for each new mask-- a very rare thing to do, yes), you'd use up _way_
less space, especially for large worlds. And besides, it takes only 2
instructions to find and read the mask also! ;)
        _Dan
...........................................................................

Fm: Randy @ Safari 71165,3600                  # 347096
To: Dan Corritore 70243,1110                   Date: 03-May-93  16:37:33

not true. You do not have as masked attribute for every tile. If you did,
you'd be stupid. Some tiles have hard attributes while only those requiring
special circumstances have masked attribs. In this case, making a seperate
tile for each instance would be a waste of space.

Randy
...........................................................................

Fm: Mark Hula 100047,110                       # 345452
To: All                                        Date: 01-May-93  09:46:30

Hi All!,

Back to my squares again (after the mess I made with my last message!). If I
have ***
          ***
          ***

by finding the first (top left) one then moving in an ever smaller concentric
square I can find out if its whole or not (solid),but I can't work out the
code!-as usual this message is as clear as mud!!

MC 'Talking Trash'

P.S Randy!,what collision technique did you use in Storm?
...........................................................................

Fm: Bob Provencher/GD SL 71621,2632            # 373881
To: Randy @ Safari 71165,3600                  Date: 11-Jun-93  19:31:30

Hi Randy -

Almost forgot about you and the collision detection.

Let's see, I've done it, but it's not very fast, I'll leave it to you guys
to optimize it, I'll just write some c++ code to give you the general idea.

first the prototypes for the functions used but not shown

class sprite
{
     bitmap image;
     bitmap mask;

     bitmap& mask() { return mask; }
}

int     rect::intersect( rect, rect );
void    bitmap::resize( rect );
void    bitmap::blit( bitmap&, rect&, int = COPY );
void    bitmap::getpixel( int, int );

int sprite::intersect( sprite& s )
{

      rect   int_rect;
      bitmap work;

      color white( 15 );

      if ( boundingbox().intersect( sprite2.boundingbox(), int_rect ) )
      {
            work.resize( intrect );
            mask().blit( work, intrect );
            sprite2.mask().blit( work, intrect, XOR );
            for ( int y = 0; y < intrect.height(); y++ )
                for ( int x = 0; x < intrect.width(); x++ )
                    if ( work.getpixel( x, y ) == white )
                         return TRUE;
            return FALSE;
      }
      else
          return FALSE;

}
...........................................................................